package com.wfm.leetcode.editor.cn;

import com.wfm.common.ListNode;

/**
 * 合并两个有序链表
 * 2025-02-26 17:18:17
 * pre
 * dummy->l1
 *         1->  3  ->  5  ->null
 *         2 -> 4  ->  6  ->null
 *        l2
 * dummy 方便返回、pre穿针引线
 * 时间复杂度：O(m+n) m是l1链表的长度，n是l2链表的长度
 * 空间复杂度：O(1)
 */
class MergeTwoSortedLists {

    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    // 方法一：穿针引线
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode res = new ListNode(-1);
        ListNode cur = res;
        while (list1!=null&&list2!=null){
            if(list1.val< list2.val){
                cur.next=list1;
                list1=list1.next;
            }else{
                cur.next=list2;
                list2=list2.next;
            }
            cur=cur.next;
        }
        cur.next=list1==null?list2:list1;
        return res.next;
    }

    // 方法二：递归
    public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        if(l1==null){
            return l2;
        }else if (l2==null){
            return l1;
        }else {
            if(l1.val< l2.val){
                l1.next = mergeTwoLists(l1.next, l2);
                return l1;
            }else{
                l2.next = mergeTwoLists(l1,l2.next);
                return l2;
            }
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new MergeTwoSortedLists().new Solution();
        
    }
}